package Other;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;

public class leet_2208 {
    public static void main(String[] args) {
        int[] nums = {32,98,23,14,67,40,26,9,96,96,91,76,4,40,42,2,31,13,16,37,62,2,27,25,100,94,14,3,48,56,64,59,33,10,74,47,73,72,89,69,15,79,22,18,53,62,20,9,76,64};
        Solution_2208 p = new Solution_2208();

        int result = p.halveArray(nums);

        System.out.printf("\n我的结果: %d", result);

    }

}

/*
*  解题思路:
*     首先计算得出数组之和,
*
*     排序(高->低) 然后取最大值进行除法,计算数组之和与目标值大小
*     重新排序取最大值进行除法,计算数组之和与目标值大小
*     以此往返,直到结果满足需求
*
* */
class Solution_2208 {
    public int halveArray(int[] nums) {
        if(nums.length==0){
            return 0;
        }
        // 步数
        int stepNum = 0;
        // 集合当前值
        double nowNum = 0;
        for(int element: nums){nowNum+=element;}
        // 集合除以2的值
        double target = nowNum/2;

        // int没办法保留小数,使用double
        List<Double> list = new ArrayList<>();
        for (int i = 0; i< nums.length;i++){
            list.add(Double.valueOf(nums[i]));
        }
        Collections.sort(list);

        // 当前index
        int index = list.size()-1;
        while (nowNum > target){
            stepNum += 1;
            double halfMaxNum = list.get(index)/2;
            list.set(index, halfMaxNum);
            nowNum = nowNum-halfMaxNum;

            if(index-1>=0 && list.get(index)<list.get(index-1)){
                index--;
            }

            // 此时索引已经到上一个值
            // 如果这个值小于第一次减半的值,重新排序计算
            if(index-1 >= 0 && list.get(index)<list.get(list.size()-1)){
                index = list.size()-1;
                Collections.sort(list);
            }
        }
        return stepNum;
    }

}
